package cn.lishiyuan.algorithm.graph;

import cn.lishiyuan.algorithm.heap.Heap;
import cn.lishiyuan.algorithm.stack.LeeStack;
import cn.lishiyuan.algorithm.stack.LinkedStack;

import java.util.*;

/**
 * 邻接矩阵
 *
 */
public class AdjacencyMatrix<V> implements Graph<V>,TopoSort<V> {

    /**
     * 顶点,可以使用 Map 存储元素与index的关系
     */
    private V[] vertices;

    /**
     * 边
     */
    private int[][] edges;

    private GraphType type;

    public AdjacencyMatrix(V[] vertices,GraphType type) {
        if (vertices==null || vertices.length == 0){
            throw new IllegalArgumentException("vertices is null or empty");
        }

        if (type == null){
            throw new IllegalArgumentException("type is null");
        }

        for (V vertex : vertices) {
            if (vertex == null) throw new IllegalArgumentException("vertex is null");
        }
        this.vertices = vertices;

        this.edges = new int[vertices.length][vertices.length];

        for (int i=0;i<this.vertices.length;i++){
            for (int j=0;j<this.vertices.length;j++){
                edges[i][j] = 0;
            }
        }

        this.type = type;
    }


    @Override
    public void addEdge(V from, V to, int weight) {
        // 查找对应元素的位置

        if (weight <= 0){
            throw new IllegalArgumentException("权重不能小于0");
        }

        int fromIndex = indexOfVertex(from);
        int toIndex = indexOfVertex(to);
        if (fromIndex == -1 || toIndex == -1){
            throw new IllegalArgumentException("顶点不存在");
        }

        if(type == GraphType.GRAPH){
            // 无向图
            edges[fromIndex][toIndex] = weight;
            edges[toIndex][fromIndex] = weight;
        }else {
            // 有向图
            edges[fromIndex][toIndex] = weight;
        }
    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, 1);
    }

    @Override
    public void removeEdge(V from, V to) {
        int fromIndex = indexOfVertex(from);
        int toIndex = indexOfVertex(to);
        if (fromIndex == -1 || toIndex == -1){
            throw new IllegalArgumentException("顶点不存在");
        }
        if(type == GraphType.GRAPH){
            // 无向图
            edges[fromIndex][toIndex] = 0;
            edges[toIndex][fromIndex] = 0;
        }else {
            // 有向图
            edges[fromIndex][toIndex] = 0;
        }

    }

    @Override
    public int getWeight(V from, V to) {

        int fromIndex = indexOfVertex(from);
        int toIndex = indexOfVertex(to);

        if (fromIndex == -1 || toIndex == -1){
            throw new IllegalArgumentException("顶点不存在");
        }

        return edges[fromIndex][toIndex];
    }

    @Override
    public boolean existsEdge(V from, V to) {
        int fromIndex = indexOfVertex(from);
        int toIndex = indexOfVertex(to);

        if (fromIndex == -1 || toIndex == -1){
            throw new IllegalArgumentException("顶点不存在");
        }


        return edges[fromIndex][toIndex] != 0;
    }

    @Override
    public int getInDegree(V vertex) {
        int index = indexOfVertex(vertex);

        if (index == -1){
            throw new IllegalArgumentException("顶点不存在");
        }

        int degree = 0;
        for (int i=0;i<vertices.length;i++){
            if(i!=index && edges[i][index] > 0){
                degree++;
            }
        }

        return degree;
    }

    @Override
    public int getOutDegree(V vertex) {
        int index = indexOfVertex(vertex);

        if (index == -1){
            throw new IllegalArgumentException("顶点不存在");
        }

        int degree = 0;
        for (int i=0;i<vertices.length;i++){
            if(i!=index && edges[index][i] > 0){
                degree++;
            }
        }
        return degree;
    }

    @Override
    public int getVertexCount() {
        return vertices.length;
    }

    @Override
    public int getEdgeCount() {
        int edgeCount = 0;

        for (int i=0;i<vertices.length;i++){
            for (int j=0;j<vertices.length;j++){
                if (i!=j &&  edges[i][j] > 0){
                    edgeCount++;
                }
            }
        }

        if (type == GraphType.GRAPH){
            // 一半
            edgeCount = edgeCount / 2;
        }

        return edgeCount;
    }

    public static class Node implements Comparable<Node>{
        public Object v;
        public int x,y;// 坐标
        public int h; // 启发函数所得估计代价
        public int dist; // 实际代价

        @Override
        public int compareTo(Node o) {
            return (h+dist) - (o.h + o.dist);
        }

        @Override
        public boolean equals(Object obj) {
            boolean eq= super.equals(obj);
            if(!eq && obj instanceof Node){
                eq = v.equals(((Node) obj).v);
            }
            return eq;
        }

    }

    @Override
    public List<V> path(V from, V to) {
        if(!(to instanceof Node toNode)){
            return Collections.emptyList();
        }
        if(!(from instanceof Node fromNode)){
            return Collections.emptyList();
        }
        // A*算法实现
        int i = indexOfVertex(from);
        int j = indexOfVertex(to);
        if ( i==-1 || j==-1){
            return Collections.emptyList();
        }

        // 当前节点到起始节点估价行数所得
        Map<Node,Integer> distance = new HashMap<>();
        // 当前节点的上个节点
        Map<Node,Node> before = new HashMap<>();
        // 当前节点是否在队列中
        List<Node> inHeap = new ArrayList<>();

        // 小顶堆

        Heap<Node> heap = new Heap<>(Heap.HeapType.MIN,vertices.length);
        fromNode.dist = 0;
        fromNode.h = h(fromNode,toNode);
        inHeap.add(fromNode);
        heap.add(fromNode);

        // 为空或者已经遇到了目标顶点
        while (!heap.isEmpty() && !heap.top().equals(to)) {
            Node top = heap.removeTop();
            int index = indexOfVertex((V) top);
            // 已经取出
            inHeap.remove(top);

            // 处理相连节点
            int[] edge = edges[index];
            for (int id = 0; id < edge.length; id++) {
                if (edge[id] > 0) {
                    Node node = ((Node) vertices[id]);

                    // 上次的估价
                    Integer dist = distance.get(node);
                    // 当前距离
                    int nowDist = edge[id] + top.dist;

                    // 计算估计代价
                    int h = h(node,toNode);
                    node.h = h;

                    // 估价函数所得代价 = h + dist

                    // 是否需要堆化
                    boolean needHeap = false;

                    if (dist == null){
                        // 第一次
                        node.dist = nowDist;
                        distance.put(node, node.dist + node.h);
                        before.put(node, top);
                        needHeap = true;
                    }else if ((nowDist+h) < dist){
                        // 已经放入过堆
                        node.dist = nowDist;
                        distance.put(node,node.dist + node.h);
                        before.put(node, top);
                        needHeap = true;
                    }

                    if (needHeap){
                        if (inHeap.contains(node)) {
                            // 更新heap
                            heap.update(node);
                        }else {
                            inHeap.add(node);
                            heap.add(node);
                        }
                    }
                }
            }

        }

        List<V> path = new ArrayList<>();
        // 逆向推断出路径
        if(before.containsKey(to)){
            path.add(to);

            V now = (V)before.get(to);
            while (now!=null){
                path.add(now);
                now = (V)before.get(now);
            }
        }

        return path;
    }

    @Override
    public int distance(V from, V to) {
        if(!(to instanceof Node toNode)){
            return -1;
        }
        if(!(from instanceof Node fromNode)){
            return -1;
        }
        // A*算法实现
        int i = indexOfVertex(from);
        int j = indexOfVertex(to);
        if ( i==-1 || j==-1){
            return -1;
        }

        // 当前节点到起始节点估价行数所得
        Map<Node,Integer> distance = new HashMap<>();
        // 当前节点的上个节点
        Map<Node,Node> before = new HashMap<>();
        // 当前节点是否在队列中
        List<Node> inHeap = new ArrayList<>();

        // 小顶堆

        Heap<Node> heap = new Heap<>(Heap.HeapType.MIN,vertices.length);
        fromNode.dist = 0;
        fromNode.h = h(fromNode,toNode);
        inHeap.add(fromNode);
        heap.add(fromNode);

        // 为空或者已经遇到了目标顶点
        while (!heap.isEmpty() && !heap.top().equals(to)) {
            Node top = heap.removeTop();
            int index = indexOfVertex((V) top);
            // 已经取出
            inHeap.remove(top);

            // 处理相连节点
            int[] edge = edges[index];
            for (int id = 0; id < edge.length; id++) {
                if (edge[id] > 0) {
                    Node node = ((Node) vertices[id]);

                    // 上次的估价
                    Integer dist = distance.get(node);
                    // 当前距离
                    int nowDist = edge[id] + top.dist;

                    // 计算估计代价
                    int h = h(node,toNode);
                    node.h = h;

                    // 估价函数所得代价 = h + dist

                    // 是否需要堆化
                    boolean needHeap = false;

                    if (dist == null){
                        // 第一次
                        node.dist = nowDist;
                        distance.put(node, node.dist + node.h);
                        before.put(node, top);
                        needHeap = true;
                    }else if ((nowDist+h) < dist){
                        // 已经放入过堆
                        node.dist = nowDist;
                        distance.put(node,node.dist + node.h);
                        before.put(node, top);
                        needHeap = true;
                    }

                    if (needHeap){
                        if (inHeap.contains(node)) {
                            // 更新heap
                            heap.update(node);
                        }else {
                            inHeap.add(node);
                            heap.add(node);
                        }
                    }
                }
            }

        }

        if(distance.containsKey(to)){
            return distance.get(to);
        }

        return -1;
    }

    /**
     * 启发函数
     * @param from
     * @param to
     * @return
     */
    private int h(Node from,Node to){
        return Math.abs(from.x - to.x) + Math.abs(from.y - to.y);
    }

    @Override
    public List<V> search(V from, V to) {
        if(Objects.isNull(from) || Objects.isNull(to)){
            throw new IllegalArgumentException("顶点不能为空");
        }

        int fromIndex = indexOfVertex(from);
        int toIndex = indexOfVertex(to);

        if (fromIndex == -1 || toIndex == -1){
            throw new IllegalArgumentException("顶点不存在");
        }

        if(Objects.equals(from,to)){
            return Collections.singletonList(from);
        }

        return dfs(fromIndex, toIndex);
    }

    /**
     * 深度优先搜索
     * @param from
     * @param to
     */
    private List<V> dfs(int from, int to){
        if(from == to){
            return Collections.singletonList(vertices[to]);
        }

        // 用栈模拟
        LeeStack<Integer> stack = new LinkedStack<>();
        stack.push(from);

        // 已访问的节点
        boolean[] visited = new boolean[vertices.length];
        Arrays.fill(visited, false);
        visited[from] = true;

        // 前向节点
        int[] prev = new int[vertices.length];
        Arrays.fill(prev, -1);

        while (!stack.isEmpty()){
            int vertex = stack.pop();
            for (int i=0;i<vertices.length;i++){
                // 存在边且未经过
                if(edges[vertex][i] > 0 && !visited[i]){
                    visited[i] = true;
                    stack.push(i);
                    prev[i]= vertex;
                    // 已找到节点
                    if(i == to){
                        int p = prev[i];
                        List<V> result = new ArrayList<>();
                        result.add(vertices[i]);
                        while (p!=-1){
                            // 已找到
                            result.add(vertices[p]);
                            p = prev[p];
                        }
                        Collections.reverse(result);
                        return result;
                    }
                }
            }
        }

        return Collections.emptyList();
    }

    /**
     * 转换成邻接表
     * @return
     */
    public AdjacencyList<V> transfer(){
        Set<V> data = new HashSet<>(Arrays.asList(vertices));

        AdjacencyList<V> adjacencyList = new AdjacencyList<>(data,type);

        for (V v : data) {
            int i = indexOfVertex(v);
            for (int j = 0;j < vertices.length;j++){
                if(i != j && edges[i][j] > 0){
                    V to = vertices[j];
                    adjacencyList.addEdge(v, to, edges[i][j]);
                }
            }
        }

        return adjacencyList;
    }

    private int indexOfVertex(V v){
        for(int i=0;i<vertices.length;i++){
            if(v.equals(vertices[i])){
                return i;
            }
        }
        return -1;
    }

    @Override
    public List<V> sort() {
        // dfs 算法,深度优先
        LeeStack<Integer> stack = new LinkedStack<>();
        boolean[] visited = new boolean[vertices.length];
        Arrays.fill(visited, false);

        // 入度为0的放入stack 出度[from][to]
        for (int i = 0; i < vertices.length; i++) {
            boolean flag = false;
            for (int j = 0; j < vertices.length; j++) {
                if(edges[j][i] > 0){
                    flag = true;
                    break;
                }
            }
            if(!flag){
                visited[i] = true;
                stack.push(i);
            }
        }

        List<V> result = new ArrayList<>();
        while (!stack.isEmpty()){
            Integer index = stack.pop();
            result.add(vertices[index]);
            // 处理完该节点后
            // 基础在少了该节点的入度的情况下 入度为0的index
            for (int i = 0; i < vertices.length; i++) {
                boolean flag = false;
                for(int j=0;j<vertices.length;j++){
                    if( index != j && edges[j][i] > 0){
                        flag = true;
                        break;
                    }
                }
                if(!flag && !visited[i]){
                    visited[i] = true;
                    stack.push(i);
                }
            }
        }

        return result;
    }
}
